import java.util.ArrayList;
import java.util.List;

/**
 * 401. 二进制手表
 * https://leetcode-cn.com/problems/binary-watch/
 */
public class Solutions_401 {
    public static void main(String[] args) {
        int turnedOn1 = 1;  // output: {"0:01", "0:02", "0:04", "0:08", "0:16", "0:32", "1:00", "2:00", "4:00", "8:00"}
        int turnedOn2 = 9;  // output: {}

        List<Integer> inputs = new ArrayList<>();
        inputs.add(turnedOn1);
        inputs.add(turnedOn2);

        for (int input : inputs) {
            List<String> result = readBinaryWatch(input);
            System.out.println(result);
        }
    }

    // 穷举 12 * 60 种可能的 时钟:分钟 时间，判断各时间用二进制手表表示时，会亮多少个灯
    public static List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();

        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                // 时钟位 1 的个数，即亮 hourBit 个灯
                int hourBit = Integer.bitCount(i);
                // 分钟位 1 的个数，即亮 minuteBit 个灯
                int minuteBit = Integer.bitCount(j);
                // 恰好组成 turnedOn 个灯
                if (hourBit + minuteBit == turnedOn) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(i);
                    sb.append(":");
                    if (j < 10) {
                        sb.append("0");
                    }
                    sb.append(j);
                    res.add(sb.toString());
                }
            }
        }
        return res;
    }
}
